This invention relates generally to computer implemented exponentiation methods and more specifically to a method for exponentiation that is faster and has lower memory requirements than other computer implemented methods.
The encryption of data for communication and storage utilizing a computer system is well known in the art. The encrypting of data is accomplished by applying a cipher to the data to be encrypted. The cipher can be known only to the encrypter and recipient (a xe2x80x9csymmetric encryptionxe2x80x9d scheme) or can be a combination of a widely known cipher coupled with a securely held cipher (a xe2x80x9cpublic keyxe2x80x9d scheme).
Some of the more popular methods, because of the ease of use and the relative invulnerability to breaking, are xe2x80x9cpublic keyxe2x80x9d systems of cryptography. These methods utilize complex mathematical formulas employing large exponents (i.e., exponents of several hundred bits or more) to increase the difficulty of unauthorized decryption.
One example of this method is the RSA method, named for its developers Rivest, Shamir, and Adleman. The RSA method is more fully described in RFC-2437 entitled xe2x80x9cPKCS #1: RSA Cryptography Specifications Version 2.0.
An RSA public key consists of two components: n, the modulus, a nonnegative integer and e, the public exponent, also a nonnegative integer. In a valid RSA public key, the modulus n is a product of two odd prime numbers p and q, and the public exponent e is an integer between 3 and nxe2x88x921 satisfying gcd (e,  lambda(n))=1, where  lambda(n)=1 cm (pxe2x88x921, qxe2x88x921), gcd (x, y) is the greatest common divisor of x and y, and 1 cm (x, y) is the least common multiple of x and y.
The RSA method involves solving the equation
c=me mod n
where (n, e) are the RSA public key; m is the message representative, an integer between 0 and nxe2x88x921, and c is the encrypted result of the exponentiation and modulo division.
The message is decrypted by the receiver by calculating m=cd mod n, where d is a private exponent. Thus, exponentiation is used both to encode and decode the message.
Another popular method of encryption is the Public Key Cryptosystem (PKC) proposed by T. ElGamal. According to this method, a prime number p is chosen and a primitive root g of p is chosen. User U selects an arbitrary number u and calculates gu=xcex1 mod p, where xcex1 is a residue of g to the u""th power modulo p. User V selects an arbitrary number v and calculates xcex2=gv mod p. The parties exchange the residues xcex1 and xcex2, and each then calculates a common key value; for User U, k=xcex2u modulo p and for User V, k=xcex1vmodulo p. The data to be encrypted is then processed arithmetically, using k to transform the data; for example, by forming the exclusive-OR of the data and k. The same operation is used to decrypt the data. Again, exponentiation is used both by the message sender and the message receiver to calculate the key that is used to encrypt or decrypt the data.
Extremely large exponential values, however, extract a cost to the user in terms of the number of multiplications required and/or the amount of computer memory that is used to perform the operations. These types of multiply operations are costly because the values to be multiplied exceed the bit-length of the processor and, thus, are implemented as multi-precision operations.
A number a raised to an exponent e can always be calculated by multiplying that number by itself the number of time represented by the exponent, or in mathematical terms:
ae=a*a*a . . . e number of times.
Another method, which is significantly faster, is the multiply chain algorithm. In this case, let e=enxe2x88x921enxe2x88x922. . .e1 e0 be an n-bit exponent ei∈{0,1}, 0xe2x89xa6ixe2x89xa6nxe2x88x921and enxe2x88x921=1. The algorithm starts with p1=a, then
pi+1=pi2 if enxe2x88x921xe2x88x92i=0 or a*pi2 if enxe2x88x921xe2x88x92i=1, where 1xe2x89xa6ixe2x89xa6nxe2x88x922.
Several methods are known in the art to reduce either the number of multiplications or the amount of computer memory needed to produce efficient exponentiation of the base value.
One method known to reduce the number of multiplication is the signed digit algorithm. In this method, the exponent is represented as a string of bits comprising the values 0 and 1. Within the bit string, sequences (or xe2x80x9crunsxe2x80x9d) of 1""s are replaced by 0""s, with a 1 being placed in the next higher bit position to the most significant bit (MSB) position of the run, and xe2x80x9cxe2x88x921xe2x80x9d being inserted in the least significant bit (LSB) position of the run. By thus efficiently recoding the exponent bit string, the expected number of multiplications is reduced from n/2 to n/3.
Another method known in the art for reducing the number of multiplications by utilizing memory, is the xe2x80x9csliding window method.xe2x80x9d In this method, the exponent is again represented as a string of 0 and 1 bits. Substrings of a predetermined fixed length are extracted and examined against a reference look-up table, which contains the base value raised to specific powers. The substring under examination is used as a reference value to look-up the value of the base raised to the power represented by the numerical value of the bit string, and the intermediate value is stored, with a reference to the position of the least significant bit in the bit string that corresponds to the pattern. After traversal of the exponent bit string, the intermediate values are then multiplied together using a multiply chain algorithm to determine the base value raised to the original exponent value.
Computer based means of encryption and decryption of communication are well known in the art. However, most advanced encryption and decryption methods are too time consuming or memory intensive, or both, for use on small devices with limited computer usage cycles or memory. As such, there is a need for a more efficient exponentiation method in terms of both the computer cycles used and the amount of memory that is consumed.
The present invention combines two recoding methods for exponentiation in a novel way. The first method is the xe2x80x9csigned digit algorithmxe2x80x9d and the second is a modified xe2x80x9csliding windowxe2x80x9d method referred to below as the string replacement method. The combination these two methods allow data to be encrypted and decrypted using a smaller number of computer cycles and less memory than prior techniques.
The subject invention is embodied in an encryption/decryption system that performs an exponentiation operation on a base number where both the base number and the exponent may be extremely large numbers (i.e., anywhere from 100 to several thousand bits long). The exponent is expressed as a bit string. The bit string is then re-coded utilizing the signed digit algorithm to eliminate runs of xe2x80x981""sxe2x80x99, by replacing them with patterns of runs of xe2x80x980""sxe2x80x99 delimited by a xe2x80x981xe2x80x99 at the bit position just above the most significant bit and xe2x80x98xe2x88x921xe2x80x99 as the least significant bit position of the run. Predetermined substring patterns are then extracted from the exponent in a manner similar to the sliding window method. The extracted strings are compared to a previously constructed look-up table containing exponent values for only a relatively small number of predetermined substrings. At each non-zero bit in the exponent, the longest such substring ending at that position is found in the lookup table and the corresponding bits in the exponent are set to zero except the rightmost bit. In this bit position is stored a reference to the corresponding entry in the look-up table. The value returned from the look-up table is the base value raised to the power represented by the substring. The exponent bit string is traversed from right to left (i.e. from the least significant bit position to the most significant bit position) until all such substrings have been extracted and corresponding references to the look-up table have been stored. The remaining bits in the exponent and intermediate values and are then processed using a multiply chain algorithm to determine the value of the base raised to the exponent.